public class Solution {

    public static void MergeSort(int start, int end, int[] array){
        if(start>=end)//容易忘记
            return;
        int mid = (end+start)/2;
        MergeSort(start,mid, array);
        MergeSort(mid+1,end, array);
        Merge(start,mid,mid+1,end,array);
    }
    public static void Merge(int start, int mid, int mid1, int end, int[] array){
        int startcopy = start;
        int[] temp = new int[array.length];
        int i = start;
        while(start<=mid && mid1<=end){
            temp[i++] = array[start]<array[mid1]?array[start++]:array[mid1++];
        }
        //如果左边剩余
        if(start<=mid){
            for(int j=start; j<=mid; j++){
                temp[i++]=array[j];
            }
        }
        //如果右边剩余
        if(mid1<=end){
            for(int j=mid1; j<=end; j++){
                temp[i++]=array[j];
            }
        }
        for(int j=startcopy; j<=end; j++){
            array[j] = temp[j];
        }
    }
    public static void main(String args[]){
        int[] array={1,5,2,6,4,7,9,3};
        MergeSort(0,array.length-1,array);
        System.out.println();
    }

}

